{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 使用最大最小距离算法进行聚类"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 最大最小距离算法基本思想\n",
    "\n",
    "最大最小距离法是模式识别中一种基于试探的类聚算法，它以欧式距离为基础，取尽可能远的对象作为聚类中心。因此可以避免K-Means法初值选取时可能出现的聚类种子过于临近的情况，它不仅能智能确定初试聚类种子的个数，而且提高了划分初试数据集的效率。  \n",
    "\n",
    "该算法以欧氏距离为基础，首先初始一个样本对象作为第1个聚类中心，再选择一个与第1个聚类中心最远的样本作为第2个聚类中心，然后确定其他的聚类中心，直到无新的聚类中心产生。最后将样本按最小距离原则归入最近的类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 最大最小距离算法步骤\n",
    "\n",
    "（1）任意选取一个样本模式作为第一聚类中心Z1。\n",
    "\n",
    "（2）选择离Z1最远欧氏距离的模式样本作为第二聚类中心Z2。\n",
    "\n",
    "（3）逐个计算每个模式样本与已确定的所有聚类中心之间的欧式距离,并选出其中的最小欧式距离。也就是说，所有的模式样本分别和Z1，Z2、…Zn求欧式距离，每个模式样本会分别得到和Z1、Z2、…Zn的欧式距离，从n者中选择小的那个。如果模式样本数是Na，那么就会选出Na个最小距离。\n",
    "\n",
    "（4）在所有最小距离中（Na个）选出一个最大距离,如果该最大值达到 ||Z1一Z2|| (Z1和Z2的欧式距离）的一定分数比值以上,（分数比值就是阈值T）则将产生最大距离的那个模式样本定义为新增聚类中心Z3，并返回步骤（3）。否则，聚类中心计算步骤结束。\n",
    "\n",
    "（5）根据实验情况，需要不断重复步骤（3）（4），直到满足阈值条件，计算出所有聚类中心{ Z1、Z2、Z3、…Zn }。\n",
    "\n",
    "（6）寻找聚类中心的运算结束后，将所有模式样本按最近欧式距离划分到相应聚类中心所代表的类别中。也就是说模式样本距哪个聚类中心近，就划分到哪个模式类中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "使用最大最小距离算法实现对样本的分类，选择的样本为二维模式，阈值为0.5。样本如下：\n",
    "\n",
    "        [0,0],[3,8],[2,2],[1,1],[5,3],[4,8],[6,3],[5,4],[6,4],[7,5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "与第一个聚类中心的距离为：0.0，索引为：0\n",
      "与第一个聚类中心的距离为：8.54400374531753，索引为：1\n",
      "与第一个聚类中心的距离为：2.8284271247461903，索引为：1\n",
      "与第一个聚类中心的距离为：1.4142135623730951，索引为：1\n",
      "与第一个聚类中心的距离为：5.830951894845301，索引为：1\n",
      "与第一个聚类中心的距离为：8.94427190999916，索引为：5\n",
      "与第一个聚类中心的距离为：6.708203932499369，索引为：5\n",
      "与第一个聚类中心的距离为：6.4031242374328485，索引为：5\n",
      "与第一个聚类中心的距离为：7.211102550927978，索引为：5\n",
      "与第一个聚类中心的距离为：8.602325267042627，索引为：5\n",
      "最小值中的最大值：4.242640687119285,索引为：6\n",
      "最小值中的最大值：2.23606797749979,索引为：2\n",
      "[1. 2. 1. 1. 3. 2. 3. 3. 3. 3.]\n",
      "[0, 5, 6]\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWoAAAD4CAYAAADFAawfAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAASz0lEQVR4nO3db4xddZ3H8c+nf/VWHIpMpQt2Lg+2GBeyQm7Z9U+IaxcDyh8frA1kNFkf9HY36sIuxKjzwPBgnhnTDWyMN8WuG68Q5V8XY6wGMWrAyhT7B2i7UZYZyqK9RAThsm2F7z44t2ynzJ8zzDlzfrfzfiWTc+/vnLn3k6b59PR3zr0/R4QAAOlaUnUAAMDMKGoASBxFDQCJo6gBIHEUNQAkblkZL3r22WdHvV4v46UB4LS0e/fu5yJicKp9pRR1vV7X2NhYGS8NAKcl2+PT7WPqAwASR1EDBTh2rOoEOJ1R1MA8dTrSOedkW6AMFDUwT/fdJz3/vLRjR9VJcLqiqIF52r598hYoWq6itv3Pth+3/ZjtO2y/pexgWJzabalel5YsybbtdtWJZtZqSQ8/nD1+6KHsOVC0WYva9rmS/klSIyIulLRU0nVlB8Pi025LzaY0Pi5FZNtmM62ybjals86SVq+WVq2StmyZvH/Llmx89ersuFP3A29G3qmPZZLeanuZpJqk/ykvEharkRGp25081u1m46m4+WZpzZos16lZTzixb80a6aabFjYfTk+zFnVEPCPpK5ImJD0r6YWI+OGpx9lu2h6zPdbh8jfehImJuY1XYf16ae9eafPmmY9rNqV9+7LjgfnKM/WxWtK1ks6X9GeSVtn+5KnHRUQrIhoR0RgcnPJTkMCM1q2b23hVVq6UbrtNGhiYev/AgHTrrdKKFQubC6evPFMffyvpvyOiExHHJd0j6f3lxsJiNDoq1WqTx2q1bDxFQ0NTj/M1NyhanqKekPTXtmu2LWmjpAPlxsJiNDyc3TUxNCTZ2bbVysZT0+1Khw5lj+3J24MHpVdeqSYXTk955qh3SbpL0qOS9vd+h5uQUIrhYempp6TXXsu2KZa0JO3cKR09Kq1dK+3ald2lsmtX9vzo0Ww/UJRcd31ExJcj4t0RcWFEfCoijpYdDEjZxIS0aVN2Vr1hQza2YUN2Nr1pU3ZrIVAUl7EKeaPRCL7mFADys707IhpT7eMj5ACQOIoaABJHUQNA4ihqAEgcRQ0AiaOoASBxFDUAJI6iBoDEUdQAkDiKGgASR1EDQOIoagBIHEUNAImjqAEgcRQ1ACQuz+K2F9jec9LPi7ZvXIBsAABJy2Y7ICIOSXqvJNleKukZSfeWGwsAcMJcpz42SvpNRLDQEAAskLkW9XWS7phqh+2m7THbY51OZ/7JAACS5lDUtldIukbSd6faHxGtiGhERGNwcLCofACw6M3ljPpKSY9GxO/KCgMAeKO5FPX1mmbaAwBQnlxFbXuVpMsl3VNuHADAqWa9PU+SIuJlSe8oOQsAYAp8MhEAEkdRA0DiKGoASBxFDQCJo6gBIHEUNQAkjqIGgMRR1ACQOIoaABJHUQNA4ihqAEgcRQ0AiaOoASBxFDUAJI6iBoDEUdQAkLi8K7ycafsu2wdtH7D9vrKDAQAyuVZ4kfSvkn4QEX/XW428VmImAMBJZi1q2wOSLpP095IUEcckHSs3FgDghDxTH+dL6kjabvtXtrf1FrudxHbT9pjtsU6nU3hQAFis8hT1MkmXSPpaRFws6WVJXzj1oIhoRUQjIhqDg4MFxwSAxStPUR+WdDgidvWe36WsuAEAC2DWoo6I30p62vYFvaGNkp4oNRUA4HV57/r4nKR2746PJyV9urxIAICT5SrqiNgjqVFuFADAVPhkIgAkjqIGgMRR1ACQOIoaABJHUQNA4ihqAEgcRQ0AiaOoASBxFDUAJI6iBoDEUdQAkDiKGgASR1EDQOIoagBIHEUNAInLVdS2n7K93/Ye22NlhwKAftLe31Z9a11Lblmi+ta62vvbhb5+3hVeJOlvIuK5Qt8dAPpce39bzfub6h7vSpLGXxhX8/6mJGn4ouFC3oOpDwCYh5EHRl4v6RO6x7saeWCksPfIW9Qh6Ye2d9tuTnWA7abtMdtjnU6nsIAAkLKJFybmNP5m5C3qD0bEJZKulPQZ25edekBEtCKiERGNwcHBwgICQMrWDayb0/ibkauoI+KZ3vaIpHslXVpYAgDoY6MbR1VbXps0Vlte0+jG0cLeY9aitr3K9hknHkv6iKTHCksAAH1s+KJhta5uaWhgSJY1NDCk1tWtwi4kSvnu+ninpHttnzj+2xHxg8ISAECfG75ouNBiPtWsRR0RT0r6y9ISAABmxO15AJA4ihoAEkdRA0DiKGoASBxFDQCJo6gBIHEUNQAkjqIGgMRR1ACQOIoaABJHUQNA4ihqAEgcRQ0AiaOoASBxFDUAJI6iBoDE5S5q20tt/8r298oMBKAc7f1t1bfWteSWJapvrau9v111pBn1W94y5VmK64QbJB2Q9PaSsgAoSXt/W837m+oe70qSxl8YV/P+piSVuoTUm9VvecuW64za9nmSPiZpW7lxAJRh5IGR10vvhO7xrkYeGKko0cz6LW/Z8k59bJX0eUmvTXeA7abtMdtjnU6niGwACjLxwsScxqvWb3nLNmtR275K0pGI2D3TcRHRiohGRDQGBwcLCwhg/tYNrJvTeNX6LW/Z8pxRf0DSNbafknSnpA/b/lapqQAUanTjqGrLa5PGastrGt04WlGimfVb3rLNWtQR8cWIOC8i6pKuk/TjiPhk6ckAFGb4omG1rm5paGBIljU0MKTW1a1kL8z1W96yOSLyH2x/SNLNEXHVTMc1Go0YGxubXzIAWERs746IxlT75nJ7niLiJ5J+UkAmAEBOfDIRABJHUQNA4ihqAEgcRQ0AiaOoASBxFDUAJI6iBoDEUdQAkDiKGgASR1EDQOIoagBIHEUNAImjqAEk7dirx6qOUDmKGkCyOi93dM5XzlHn5cW9vB9FDSBZ9x28T8//7/PacWhH1VEqRVEDSNb2PdsnbRerPIvbvsX2L23vtf247VsWIhiAYrX3t1XfWteSW5aovrWu9v521ZFm1Nrd0sOHH5YkPfT0Q2rtblWcqDqzLsVl25JWRcRLtpdL+rmkGyLiF9P9DktxAWlp72+reX9T3ePd18dqy2tJrUPYvL+pu564S6HQsVePTcp6Qm15TSuWrpBlfeI9n9DXr/56BUnLMdNSXHkWt42IeKn3dHnvJ/9CiwAqN/LAyBuKr3u8q5EHRipK9EY3v/9mrVm1Rt3j3SlLWtLr+9asWqOb3n/TAiesTq45attLbe+RdETSjyJi1xTHNG2P2R7rdBb3FVogNRMvTMxpvArr37Fee/9hrzZfsnnG45qXNLXvH/dp/TvWL1Cy6uUq6oh4NSLeK+k8SZfavnCKY1oR0YiIxuDgYMExAczHuoF1cxqvysplK3XbR2/TwMqBKfcPrBzQrR+9VSuWrljgZNWa010fEfEHSQ9KuqKUNABKMbpxVLXltUljteU1jW4crSjRzIbOHJpyvH5mfWGDJCLPXR+Dts/sPX6rpMslHSw5F4ACDV80rNbVLQ0NDMmyhgaGkrqQeLLu8a4OPXdIkmR50vbgcwf1yvFXKstWlWU5jlkr6Zu2lyor9u9ExPfKjQWgaMMXDSdZzKfa+eudOvrqUa1921rtuG6HNpy7QY8884iuvfNaPfvSs9r5m536+Ls/XnXMBTVrUUfEPkkXL0AWANDECxPa9BebtO3qbTpj5RmSpA3nbtDBzx7U5vs3a/wP4xUnXHiz3kf9ZnAfNQDMzbzuowYAVIuiBoDEUdQAkDiKGgASR1EDQOIoagBIHEUNAImjqAEgcRQ1ACSOogaAxFHUAJA4ihoAEkdRA0DiKGoASFyeFV7eZftB20/Yftz2DQsRDAVqt6V6XVqyJNu221UnAjAHeVZ4+ZOkmyLiUdtnSNpt+0cR8UTJ2VCEdltqNqVuN3s+Pp49l6Th9Ff7AJDjjDoino2IR3uP/yjpgKRzyw6GgoyM/H9Jn9DtZuMA+sKc5qht15Uty7Vrin1N22O2xzqdTkHxMG8TE3MbB5Cc3EVt+22S7pZ0Y0S8eOr+iGhFRCMiGoODg0VmxHysWze3cQDJyVXUtpcrK+l2RNxTbiQUanRUqtUmj9Vq2TiAvpDnrg9Lul3SgYj4avmRUKjhYanVkoaGJDvbtlpcSAT6yKyrkNv+oKSfSdov6bXe8Jci4vvT/Q6rkAPA3My0Cvmst+dFxM8lufBUAIBc+GQiACSOogaAxFHUAJA4ihoAEkdRA0DiKGoASBxFDQCJo6gBIHEUNQAkjqIGgMRR1ACQOIoaABJHUQNA4ihqAEgcRQ0AiaOoASBxeZbi+obtI7YfW4hAfaHdlup1acmSbNtuV50IwGkszxn1v0u6ouQc/aPdlppNaXxcisi2zSZlDaA0sxZ1RPxU0u8XIEt/GBmRut3JY91uNg4AJShsjtp20/aY7bFOp1PUy6ZnYmJu4wAwT4UVdUS0IqIREY3BwcGiXjY969bNbRwA5om7PuZqdFSq1SaP1WrZOACUgKKeq+FhqdWShoYkO9u2Wtk4AJRg2WwH2L5D0ocknW37sKQvR8TtZQdL2vAwxQxgwcxa1BFx/UIEAQBMjakPAEgcRQ0AiaOoASBxFDUAJI6iBoDEUdQAkDiKGgASR1EDQOIoagBIHEUNAImjqAEgcRQ1ACQuvaI+dqzqBACQlLSKutORzjkn2wIAJKVW1PfdJz3/vLRjR9VJACAZaRX19u2TtwCAfEVt+wrbh2z/2vYXSknSakkPP5w9fuih7DkAYPaitr1U0r9JulLSeyRdb/s9837nZlM66yxp9Wpp1Sppy5bJ+7dsycZXr86OO3U/ACwSec6oL5X064h4MiKOSbpT0rXzfuebb5bWrJG63exnKif2rVkj3XTTvN8SAPpRnqI+V9LTJz0/3BubxHbT9pjtsU6euzbWr5f27pU2b575uGZT2rcvOx4AFqHCLiZGRCsiGhHRGBwczPdLK1dKt90mDQxMvX9gQLr1VmnFiqJiAkDfyVPUz0h610nPz+uNFWdoaOrxer3QtwGAfpSnqB+R9Oe2z7e9QtJ1kv6zsATdrnToUPbYnrw9eFB65ZXC3goA+tGsRR0Rf5L0WUk7JR2Q9J2IeLywBDt3SkePSmvXSrt2SRHZdu3abHznzsLeCgD60bI8B0XE9yV9v5QEExPSpk3Stm3SGWdkYxs2ZGfTmzdL4+OlvC0A9AtHROEv2mg0YmxsrPDXBYDTle3dEdGYal9aHyEHALwBRQ0AiaOoASBxpcxR2+5IerNXAc+W9FyBccrUT1ml/srbT1ml/srbT1ml/so7n6xDETHlpwVLKer5sD023YR6avopq9Rfefspq9Rfefspq9RfecvKytQHACSOogaAxKVY1P20YkA/ZZX6K28/ZZX6K28/ZZX6K28pWZObowYATJbiGTUA4CQUNQAkLpmiXpAFdAti+xu2j9h+rOoss7H9LtsP2n7C9uO2b6g600xsv8X2L23v7eW9pepMs7G91PavbH+v6iyzsf2U7f2299hO+gt5bJ9p+y7bB20fsP2+qjNNx/YFvT/TEz8v2r6xsNdPYY66t4Duf0m6XNlSX49Iuj4inqg02DRsXybpJUn/EREXVp1nJrbXSlobEY/aPkPSbkkfT/jP1pJWRcRLtpdL+rmkGyLiFxVHm5btf5HUkPT2iLiq6jwzsf2UpEZEJP8BEtvflPSziNjW+y78WkT8oeJYs+r12TOS/ioiCvn6z1TOqMtZQLckEfFTSb+vOkceEfFsRDzae/xHZd8p/oY1L1MRmZd6T5f3fqo/m5iG7fMkfUzStqqznE5sD0i6TNLtkhQRx/qhpHs2SvpNUSUtpVPUuRbQxfzYrku6WNKuiqPMqDeVsEfSEUk/ioiU826V9HlJr1WcI6+Q9EPbu203qw4zg/MldSRt700rbbO9qupQOV0n6Y4iXzCVokbJbL9N0t2SboyIF6vOM5OIeDUi3qtsfc5LbSc5vWT7KklHImJ31Vnm4IMRcYmkKyV9pjeNl6Jlki6R9LWIuFjSy5KSvnYlSb0pmmskfbfI102lqMtfQHcR68313i2pHRH3VJ0nr95/dR+UdEXFUabzAUnX9OZ975T0YdvfqjbSzCLimd72iKR7lU07puiwpMMn/W/qLmXFnborJT0aEb8r8kVTKepyF9BdxHoX526XdCAivlp1ntnYHrR9Zu/xW5VdYD5YaahpRMQXI+K8iKgr+zv744j4ZMWxpmV7Ve+CsnrTCB+RlOSdSxHxW0lP276gN7RRUpIXwE9xvQqe9pByrplYtoj4k+0TC+gulfSNQhfQLZjtOyR9SNLZtg9L+nJE3F5tqml9QNKnJO3vzftK0pd662CmaK2kb/aunC9Rtphy8re99Yl3Sro3+7dbyyR9OyJ+UG2kGX1OUrt38vakpE9XnGdGvX/8Lpe0pfDXTuH2PADA9FKZ+gAATIOiBoDEUdQAkDiKGgASR1EDQOIoagBIHEUNAIn7P/v2hp18cayZAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import math\n",
    "import numpy as np\n",
    "from matplotlib import pyplot\n",
    "\n",
    "\n",
    "def calcuDistance(data1, data2):\n",
    "    \"\"\"  计算两个模式样本之间的欧式距离 \"\"\"\n",
    "    distance = 0\n",
    "    for i in range(len(data1)):\n",
    "        distance += pow((data1[i] - data2[i]), 2)\n",
    "    return math.sqrt(distance)\n",
    "\n",
    "\n",
    "def maxmin_distance_cluster(data, Theta):\n",
    "    \"\"\"\n",
    "    :param data: 输入样本数据,每行一个特征\n",
    "    :param Theta:阈值，一般设置为0.5，阈值越小聚类中心越多\n",
    "    :return:样本分类，聚类中心\n",
    "    \"\"\"\n",
    "    maxDistance = 0\n",
    "    start = 0  # 初始选一个中心点\n",
    "    index = start  # 相当于指针指示新中心点的位置\n",
    "    k = 0  # 中心点计数，也即是类别\n",
    "\n",
    "    dataNum = len(data)     # 样本数\n",
    "    distance = np.zeros((dataNum,))\n",
    "    minDistance = np.zeros((dataNum,))\n",
    "    classes = np.zeros((dataNum,))\n",
    "    centerIndex = [index]\n",
    "\n",
    "    ptrCen = data[0] # 初始选择第一个为聚类中心点\n",
    "    # 寻找第二个聚类中心，即与第一个聚类中心最大距离的样本点\n",
    "    for i in range(dataNum):\n",
    "        ptr1 = data[i]\n",
    "        d = calcuDistance(ptr1, ptrCen)\n",
    "        distance[i] = d\n",
    "        classes[i] = k + 1\n",
    "        if (maxDistance < d):\n",
    "            maxDistance = d\n",
    "            index = i  # 与第一个聚类中心距离最大的样本\n",
    "        print(\"与第一个聚类中心的距离为：{}，索引为：{}\".format(distance[i], index))  # 打印欧式距离及新的聚类中心\n",
    "    minDistance = distance.copy()\n",
    "    maxVal = maxDistance\n",
    "    while maxVal > (maxDistance * Theta):\n",
    "        k = k + 1\n",
    "        centerIndex += [index]  # 新的聚类中心\n",
    "        for i in range(dataNum):\n",
    "            ptr1 = data[i]\n",
    "            ptrCen = data[centerIndex[k]]\n",
    "            d = calcuDistance(ptr1, ptrCen)\n",
    "            distance[i] = d\n",
    "            # 按照当前最近邻方式分类，哪个近就分哪个类别\n",
    "            if minDistance[i] > distance[i]:\n",
    "                minDistance[i] = distance[i]\n",
    "                classes[i] = k + 1\n",
    "        # 寻找minDistance中的最大距离，若maxVal > (maxDistance * Theta)，则说明存在下一个聚类中心\n",
    "        index = np.argmax(minDistance)\n",
    "        print(\"最小值中的最大值：{},索引为：{}\".format(minDistance[i], index))\n",
    "        maxVal = minDistance[index]\n",
    "    return classes, centerIndex\n",
    "\n",
    "data = [[0, 0], [3, 8], [2, 2], [1, 1], [5, 3], [4, 8], [6, 3], [5, 4], [6, 4], [7, 5]]\n",
    "Theta = 0.5\n",
    "classes, centerIndex = maxmin_distance_cluster(data, Theta)\n",
    "print(classes)\n",
    "print(centerIndex)\n",
    "\n",
    "color = ['r', 'b', 'g']\n",
    "for i in range(len(classes)):\n",
    "    pyplot.scatter(data[i][0], data[i][1], c=color[int(classes[i])-1])  # 画出样本数据\n",
    "\n",
    "for i in range(len(centerIndex)):\n",
    "    pyplot.scatter(data[centerIndex[i]][0], data[centerIndex[i]][1], c=color[i], marker='*', s=150) # 画出中心点\n",
    "pyplot.show()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}